package com.fengye.algorithms.leecode.dp;

import java.util.*;

/**
 * @Author fengye
 * @Date 2023/4/8 11:30
 **/
public class WordBreak139 {
    public static void main(String[] args) {
        String s = "appledappleatop";
        List<String> dict = Arrays.asList("app", "led", "a", "apple", "top");
        new WordBreak139().wordBreak2(s, dict).stream().forEach(System.out::println);
    }

    public List<String> wordBreak2(String s, List<String> wordDict) {
        // 去重
        Set<String> dict = new HashSet<String>(wordDict);
        List<String> result = new ArrayList<>();
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1;i<=s.length();i++) {
            for(int j=0;j<i;j++) {
                String sub = s.substring(j, i);
                // j已经包含在dick中，并且j-i字串也包含在dict中，那么dp[i]=true
                if(dp[j] && dict.contains(sub)) {
                    dp[i] = true;
                    if(!result.contains(sub))
                        result.add(sub);
                    break;
                }
            }
        }

        if(dp[s.length()]) {
            return result;
        }

        return null;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        // 去重
        Set<String> dict = new HashSet<String>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1;i<=s.length();i++) {
            for(int j=0;j<i;j++) {
                // j已经包含在dick中，并且j-i字串也包含在dict中，那么dp[i]=true
                if(dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }


}
